HW#2 --- last modified February 28 2019 23:10:17..

Solution set.

Due date: Feb 28

Files to be submitted:
  Hw2.zip

Purpose: To gain experience with DFAs, NFAs, and regular expressions. To be able to use the Pumping Lemma.

Related Course Outcomes:

(2) Construct deterministic and non-deterministic machines for various languages.

(3) Describe a language in terms of a regular expression.

(4) Find a regular expression for a language described by a finite automaton and conversely.

(5) Construct a deterministic finite automaton from a non-deterministic one.

(6) Minimize a deterministic automaton

(7) Be able to use a pumping lemma to show that some languages are not regular and/or not context-free Use closure properties to simplify proofs of non-regularity of languages.

Specification:

Submit your work below in the file Hw2.zip.

1. Do the book problems pg 47 #7; pg 55 # 7 and 10. Give your solution to each problem as a separate JFLAP file that you include in your ZIP file.

2. In the file DFA710.pdf (put this in Hw2.zip) show step by step the process of converting the machines from page 55 problems 7 and 10 to DFAs. Then do state minimization by hand on the answers you get.

3. In the file REGEX710.pdf (put this in Hw2.zip) show step by step the process of converting the machines from from page 55 problems 7 and 10 to regular expressions.

4. In the file REGEX.pdf (put this in Hw2.zip) do problems pg88 #13 and pg123 #15.

5. In the file NFA.pdf (put this in Hw2.zip) show step by step the results of converting your problem #13 answer above to equivalent NFAs.

If I say step by step in the above and you do not show the steps according to the algorithm convered in class/in the book, you will receive 0 credit for that problem!

Point Breakdown